package dp;

import java.util.ArrayList;

public class D230821 {
    // 数字字符串转化成IP地址
    // 枚举 IP地址中，三个 . 的位置
    // 将IP分为 4 段，对这 4 段进行校验，符合就拼接起来。
    // 时间：O(N3)
    // 空间：O(N)
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<String>();
        int n = s.length();
        // 遍历IP的点可能的位置（第一个点）
        // 要保证第一个点 前面至少有一个数字，后面至少有三个数字
        for(int i = 1; i < 4 && i < n - 2; i++){
            // 第二个点的位置
            for(int j = i + 1; j < i + 4 && j < n - 1; j++){
                // 第三个点的位置
                for(int k = j + 1; k < j + 4 && k < n; k++){
                    // 最后一段剩余数字不能超过3
                    if(n - k >= 4)
                        continue;
                    // 从点的位置分段截取
                    String a = s.substring(0, i);
                    String b = s.substring(i, j);
                    String c = s.substring(j, k);
                    String d = s.substring(k);
                    // IP每个数字不大于255
                    if(Integer.parseInt(a) > 255 || Integer.parseInt(b) > 255 || Integer.parseInt(c) > 255 || Integer.parseInt(d) > 255)
                        continue;
                    //排除前导0的情况
                    if((a.length() != 1 && a.charAt(0) == '0') || (b.length() != 1 && b.charAt(0) == '0') ||  (c.length() != 1 && c.charAt(0) == '0') || (d.length() != 1 && d.charAt(0) == '0'))
                        continue;
                    //组装IP地址
                    String temp = a + "." + b + "." + c + "." + d;
                    res.add(temp);
                }
            }
        }
        return res;
    }


    // 编辑距离(一)
    // 时间：O(MN)
    // 空间：O(MN)
    public int editDistance (String str1, String str2) {
        int n = str1.length();
        int m = str2.length();
        // dp[i][j] 表示，str1 的前 i 个字符 转为 str2 的前 j 个字符 的最少操作数
        int[][] dp = new int[n + 1][m + 1];
        // 多定义一行一列
        // 初始化，空串变为 str1 或 str2 所需的编辑距离
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= m; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    // 相同
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 不相同，从替换、插入、删除 三种操作中选一个操作数最小的值
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1,
                            Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[n][m];
    }
}
